package day1.bitmap;

import java.util.HashSet;

/**
 * @author pacai
 * @version 1.0
 * 位图
 */
public class BitMap {
    private long[] bits;

    public BitMap(int max) {
        bits = new long[(max +  64) >> 6];//(max + 64) / 64
    }

    public void add(int num){
        //num >> 6 -> num / 64 找到放入哪个数中
        //num & 63 -> num % 64 本质就是将高于63的位数丢弃(适用于%2^n的数)
        //1L << num & 63 找到num值对应的位数
        //|= 将对应位上的二进制位置为1
        bits[num >> 6] |= (1L << (num & 63));
    }

    //~(1L << (num & 63)) 将要删除的位置设为0
    //&= 运算将对应位数改为0（无论该位是0/1都会置为0）不用额外判断
    public void remove(int num){
        bits[num >> 6] &= ~(1L << (num & 63));
    }

    //&运算需要两个位都为1才为1 只要对应位上为1就代表存储此值
    public boolean contains(int num){
        return (bits[num >> 6] & (1L << (num & 63))) != 0;
    }

    public static void main(String[] args) {
        System.out.println("测试开始");
        int max = 10000;
        BitMap bitMap = new BitMap(max);
        HashSet<Integer> set = new HashSet<>();
        int testTimes = 1000000;
        for (int i = 0; i < testTimes; i++) {
            int num = (int)(Math.random() * (max + 1));
            double decide = Math.random();
            if(decide < 0.33){
                set.add(num);
                bitMap.add(num);
            }else if(decide < 0.66){
                set.remove(num);
                bitMap.remove(num);
            }else{
                if(bitMap.contains(num) != set.contains(num)){
                    System.out.println("Oops");
                    break;
                }
            }
        }
        System.out.println("测试结束");
    }
}
